package com.ronz.stack;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Description 使用栈实现一个逆波兰计算器，该计算器输入为中缀表达式，然后将中缀表达式转换为后缀进行计算。
 *              计算器基本功能包括：
 *                  - 基本的加减乘除
 *                  - 支持小数、多位数
 * @Author Ronz
 * @Date 2020/12/31 9:53
 * @Version 1.0
 */
public class No4_Stack_InfixToPostfixExpression {

    public static void main(String[] args) {
        // 中缀表达式
        String expression = "1.1+((12 +3)*2.4) -5";
        // 获取中缀表达式的元素列表
        List<String> list = getList(expression);
        // 中缀表达式转换到后缀表达式
        List<String> postExpression = getPostExpression(list);
        // 使用后缀表达式计算
        Float res = calculate(postExpression);
        System.out.println(expression + " = " + res);
    }

    /**
     * @Description 根据中缀表达式的 list 集合来获得后缀表达式的 list 集合
     */
    public static List<String> getPostExpression(List<String> list){
        Stack<String> s1 = new Stack<>();
        // 因为 s2 中最终存放的元素的倒序才是后缀表达式，用 list 来代替 stack 则无需反转
        ArrayList<String> s2 = new ArrayList<>();

        // 遍历列表
        for (String item : list){
            if (item.matches("([1-9]\\d*\\.?\\d+)|(0\\.\\d*[1-9])|(\\d+)")){      // 如果是数字，直接入栈
                s2.add(item);
            }else if ("(".equals(item)){    // 如果是左括号，直接入栈
                s1.push(item);
            }else if (")".equals(item)){    // 如果是右括号
                // s1 需要 pop 出栈顶的元素，然后 push 到 s2 中，直到遇见左括号抵消右括号
                while (!"(".equals(s1.peek()) && s1.size() > 0){
                    s2.add(s1.pop());
                }
                s1.pop();   // pop 出左括号
            }else{      // 如果是运算符
                while(true){
                    // 如果 s1 为空或者栈顶为 "("，直接入栈
                    if (s1.isEmpty() || "(".equals(s1.peek())){
                        s1.push(item);
                        break;
                    }else{      // 如果不为空，且栈顶不为 "("
                        // 如果运算符优先级大于 s1 栈顶，直接入栈
                        if (getPriority(item) > getPriority(s1.peek())){
                            s1.push(item);
                            break;
                        }else{
                            // 如果运算符优先级小于 s1 栈顶，则栈顶元素出栈并入栈到 s2 中，然后继续循环判断
                            s2.add(s1.pop());
                        }
                    }
                }

            }
        }

        // 把 s1 的全部读出来
        while (!(s1.isEmpty())){
            s2.add(s1.pop());
        }
        return s2;
    }

    /**
     * @Description 将中缀表达式转换到 list 集合中存放
     * 之所以这么做，主要是为了方便对中缀表达式中两位数以上的数字进行处理
     */
    public static List<String> getList(String str){
        ArrayList<String> list = new ArrayList<>();
        StringBuilder numStr = new StringBuilder();
        str = str.replaceAll(" ", "");  // 去掉表达式中的空格
        // 遍历表达式字符
        for (int i=0; i<str.length(); i++){
            char c = str.charAt(i);
            // 判断当前字符是数字还是符号
            if (!(48 < c && c < 57) && !".".equals(c+"")){     // 如果是符号
                list.add(c + "");               // 把字符转为字符串后，添加到 list
            }else{                              // 如果是数字
                numStr.append(c);

                // 需要判断当前字符的下个字符是否依然是数字
                // 但是首先需要判断当前字符还有没有下一个字符，即是否是最后一个字符
                if (!(i == str.length() - 1)){      // 如果不是最后一个字符
                    char c1 = str.charAt(i + 1);
                    if (!(c1 > 48 && c1 < 57) && !".".equals(c1+"")){     // 如果不是数字和小数点，就将拼接好的数字添加到 list
                        list.add(numStr.toString());
                        numStr = new StringBuilder();
                    }
                }else{    // 如果是最后一个字符，就添加到 list
                    list.add(numStr.toString());
                }
            }
        }
        return list;
    }

    /**
     * @Description 根据后缀表达式计算结果
     */
    public static Float calculate(List<String> list){
        Stack<Float> numStack = new Stack<>();
        for (String item : list){
            if (item.matches("([1-9]\\d*\\.?\\d+)|(0\\.\\d*[1-9])|(\\d+)")){
                numStack.push(Float.valueOf(item));
            }else{
                Float num_1 = numStack.pop();
                Float num_2 = numStack.pop();
                switch (item){
                    case "+":
                        numStack.push(num_2 + num_1);
                        break;
                    case "-":
                        numStack.push(num_2 - num_1);
                        break;
                    case "*":
                        numStack.push(num_2 * num_1);
                        break;
                    case "/":
                        numStack.push(num_2 / num_1);
                        break;

                        default:
                            throw new RuntimeException("运算符错误！");

                }
            }
        }
        return numStack.pop();
    }

    /**
     * @Description 获取运算符优先级
     */
    public static int getPriority(String operation){
        switch (operation){
            case "+":
            case "-":
                return 0;
            case "*":
            case "/":
                return 1;
            default:
                return -1;
        }
    }
}
